1446C - Xor Tree - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

#define all(x) begin(x),end(x)

template<class T>
    using iset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

void solve(){
    int n;
    cin>>n;
    vector<long long> a(n);
    for(auto&i:a){
	cin>>i;
    }
    sort(all(a));
    
    auto rec=[&](auto&&rec,int begi,int endi,long long TARGET)
    {
	if(endi-begi<=1)return 0;
	
	int pos=begi-1;
	for(int jump=__lg(endi-1-begi);jump>=0;jump--){
	    int posjump=pos+(1<<jump);
	    if(posjump<endi&&((a[posjump]&TARGET)==0))pos=posjump;
	}
	pos++;

	int removeRight=max(0,endi-pos-1);
	int removeLeft=max(0,pos-begi-1);
	if(TARGET==0){
	    return min(removeLeft,removeRight);
	}
	
	int solLeft=rec(rec,begi,pos,TARGET>>1)+removeRight;
	int solRight=rec(rec,pos,endi,TARGET>>1)+removeLeft;
	return min(solLeft,solRight);
    };

    int sol=rec(rec,0,n,1ll<<32);
    cout<<sol<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int numberOfTests=1;
    //cin>>numberOfTests;
    while(numberOfTests--){
	solve();
    }
}